#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*- 
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab                                     
#http://www.careercup.com/question?id=14581715
#Google interview question
""" 
Given an array of intergers. Write a program to print all the permutations of the numbers in the array. The output should be sorted in a non-increasing order. For example for the array { 12, 4, 66, 8, 9}, the output should be:

9866412

9866124

9846612

....

....

1246689
"""         
import os, re, sys, getopt
import time
from utils import *

def print_permutation_david_helper(prefix, arr, result):
    if not len(arr):
        result.append("".join(prefix))
        return
    else:
        for i in range(0, len(arr)):
            prefix.append(arr[i])
            del arr[i]
            print_permutation_david_helper(prefix, arr, result)
            arr.insert(i, prefix.pop())

@time_profile
def print_permutations_david(arr):
    arr.sort(key = lambda x: str(x))
    arr.reverse()
    arr = [str(i) for i in arr]
    result = []
    print_permutation_david_helper([], arr, result)
    return result
        
def permutation_helper(prefix, arr, result):
    if len(arr) > 0:
        permutation_helper(prefix + str(arr[-1]), arr[:-1], result)
        for i in range(len(arr) - 2, -1, -1):
            permutation_helper(prefix + str(arr[i]), arr[:i] + arr[i + 1:], result)
    else:
        result.append(prefix)
        
@time_profile
def print_permutations_lobatt(arr):
    if len(arr) <= 0: return
    a = sorted(arr, key=lambda x: str(x))
    result = []
    prefix = ""
    permutation_helper(prefix, a, result)
    return result

if __name__ == '__main__':
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'd:', ['date=', 'debug'])               
        for opt, arg in opts:                                                            
            if opt in ['-d', '--date']: date = datetime.date(int(arg[:4]), int(arg[4:6]), int(arg[6:8]))
            elif opt in ['--debug']:
                debug = True
    except getopt.GetoptError, err:                                                      
        print str(err)
        print __doc__                                                                    
        sys.exit(1)
        
    for i in range(0, 15):
        arr = random_arr(10, 1, 20)
        arr = list(set(arr))
        lobatt = print_permutations_lobatt(arr)
        david = print_permutations_david(arr)
        print arr
        if lobatt == david: 
            print_pass()
        else:
            print_fail()
            print lobatt
            print david
